package uestc.lj.basic.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 求一颗二叉树的最大宽度
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code03_getMaxWidth {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int getMaxWidth(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		HashMap<Node, Integer> levelMap = new HashMap<>();
		levelMap.put(head, 1);
		//当前层
		int curLevel = 1;
		//当前层节点数量
		int curLevelNodes = 0;

		int maxWidth = Integer.MIN_VALUE;
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			//当前节点所在的层
			int curNodeLevel = levelMap.get(cur);
			if (curNodeLevel == curLevel) {
				curLevelNodes++;
			} else {
				maxWidth = Math.max(maxWidth, curLevelNodes);
				curLevel++;
				curLevelNodes = 1;
			}
			if (cur.left != null) {
				levelMap.put(cur.left, curNodeLevel + 1);
				queue.add(cur.left);
			}
			if (cur.right != null) {
				levelMap.put(cur.right, curNodeLevel + 1);
				queue.add(cur.right);
			}
		}
		return maxWidth;
	}

	public static int getMaxWidth2(Node head) {
		if (head == null) {
			return 0;
		}
		int maxWidth = Integer.MIN_VALUE;
		Queue<Node> queue = new LinkedList<>();

		Node curLevelEndNode = head;
		Node nextLevelEndNode = null;
		int curLevelNodes = 0;
		queue.add(head);
		while (!queue.isEmpty()) {
			head = queue.poll();
			if (head.left != null) {
				queue.add(head.left);
				nextLevelEndNode = head.left;
			}
			if (head.right != null) {
				queue.add(head.right);
				nextLevelEndNode = head.right;
			}
			curLevelNodes++;
			if (curLevelEndNode == head) {
				maxWidth = Math.max(maxWidth, curLevelNodes);
				curLevelEndNode = nextLevelEndNode;
				nextLevelEndNode = null;
				curLevelNodes = 0;
			}
		}
		return maxWidth;
	}
}
